/* 
    求所有数比左边数大的数的和
    */
let sum = 0;
let smallSum = function (arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let mid = Math.floor(arr.length / 2);

    let left = arr.slice(0, mid);
    let right = arr.slice(mid);

    return merge(smallSum(left), smallSum(right));
};

function merge(leftArr, rightArr) {
    let helpArr = [];
    while (leftArr.length && rightArr.length) {
        if (leftArr[0] < rightArr[0]) {
            let temp = leftArr.shift();
            sum += temp * rightArr.length;
            helpArr.push(temp);
        } else {
            helpArr.push(rightArr.shift());
        }
    }
    if (leftArr.length) {
        // console.log(leftArr);
        leftArr.forEach((element) => {
            helpArr.push(element);
        });
    } else {
        rightArr.forEach((element) => {
            helpArr.push(element);
        });
    }
    return helpArr;
}

let arr = [-1, -1, -3];
smallSum(arr);
console.log(sum);

// let violence = function (array) {
//     // 暴力求解
//     let sum = 0;
//     for (let i = 0; i < array.length - 1; i++) {
//         for (let j = i + 1; j < array.length; j++) {
//             if (array[i] < array[j]) {
//                 sum += array[i];
//             }
//         }
//     }
//     return sum;
// };

// // let arr = [2, -8, 4];
// // let res = violence(arr);
// // console.log(res);

// let check = function (testTimes, methodTested, violence) {
//     // 验证函数
//     while (testTimes) {
//         let arrTest = generate(5, 10);
//         let resA = violence(arrTest);
//         let sort = methodTested(arrTest);
//         if (resA !== sum) {
//             console.log(arrTest, resA, sum, sort);
//             return false;
//         }
//         testTimes--;
//     }
//     return true;
// };

// function generate(maxSize, maxValue) {
//     // 测试用例
//     let size = Math.floor((maxSize + 1) * Math.random());
//     let resArr = new Array(size);

//     for (let index = 0; index < resArr.length; index++) {
//         let temp = Math.floor((maxValue + 1) * Math.random()) - Math.floor((maxValue + 1) * Math.random());
//         resArr[index] = temp;
//     }
//     return resArr;
// }

// let res = check(1000, smallSum, violence);
// console.log(res);
